package com.structure.algorithm;


/**
 * 归并排序
 * Created by 乔磊 on 2015/11/26.
 */
public class MergeSort {
    //如果两个数组是有序的直接调用merge即可完成排序
    public static int[] merge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }
        while (i < a.length) {
            result[k++] = a[i++];
        }
        while (j < b.length) {
            result[k++] = b[j++];
        }
        return result;
    }
    //如果两个数组不是有序的，在两个数组合并后，需要对生成的数组进行排序处理
    public static int[] sortMerger(int[] a, int first, int last) {
        if (first < last) {
            int mid = (last + first) /2;//取数组的中间位置
            sortMerger(a, first, mid);//左半边排序
            sortMerger(a, mid + 1, last);//右半边排序
            merge(a, first, mid, last);//合并
        }
        return a;
    }
    private static void merge(int[] a, int first, int mid, int last) {
        int size = last - first + 1;
        int arr[] = new int[size];
        int i = first, k = 0;
        int j = mid + 1;
        while (i <= mid && j <= last) {
            if (a[i] <= a[j]) {
                arr[k++] = a[i++];
            } else {
                arr[k++] = a[j++];
            }
        }
        while (i <= mid)
            arr[k++] = a[i++];
        while (j <= last)
            arr[k++] = a[j++];
        // 数组arr[]里面已经保存了排好序的元素
        for (int x = 0; x < last - first + 1; x++) { // q-p+1 == size
            a[first + x] = arr[x];
        }
    }
    public static void main(String[] args){
        int[] a = new int[]{1,2,3,4,5,6,7,8,9};
        int[] b = new int[]{6,5,7,8,3,9,12};
        int[] c = merge(a,b);
        int[] d = sortMerger(c,0,c.length -1);
        for (int dd:d){
            System.out.print(dd);
        }
    }
}
